Erasure channel is an important channel model. During data transmission, if an error occurs in check of a data packet received by a receiver, then erroneous data segments will be discarded, i.e., erased. Transmitting files over the Internet is a mode of communication by data packet. Generally, each data packet is either received by the receiver correctly or not received by the receiver at all. In the transmission control protocol (TCP), error detection and retransmission mechanism is adopted against packet loss in network, that is, feedback channel from an input terminal to an output terminal is used to control data packets that are required to be retransmitted. When the receiver detects packet loss, it generates a retransmission control signal until a complete data packet is received; and when the receiver receives the data packet, it also generates a receiving acknowledgement signal. A sender, on the other hand, tracks each data packet until the fed back acknowledgement signal is received, otherwise the acknowledgement signal will be retransmitted.
A data broadcast service based on streaming mode and file downloading mode is a point-to-multipoint service, in which feedback is not allowed and traditional error detection and retransmission mechanism cannot be used, and forward error correction (FEC) is required to be used to ensure reliable transmission of data. The FEC in a classical application layer includes Reed-Solomon (RS) codes and digital fountain codes. The RS codes with higher encoding and decoding complexity typically apply to only cases where code length is smaller. Luby transform (LT) codes and Raptor codes are two types of practically applicable digital fountain codes. The LT codes have linear encoding and decoding time, which is an essential improvement as compared to the RS codes, and the Raptor codes use pre-encoding technology and thus have higher decoding efficiency. The multimedia broadcast/multicast service (MBMS) and digital video broadcasting (DVB) of the 3rd Generation Partnership Project (3GPP) uses the Raptor codes from Digital Fountain Company as their FEC encoding scheme.
If the first k bits of the encoded code word are the same as information bits, then the code is called a system code. The encoding process is a process where the K information bits generate a code length with N bits, and N-K check bits are added in order to achieve error detection and correction. The LT codes do not support the encoding mode of the system code, thus it is difficult for the LT codes to satisfy certain actual FEC coding requirements. The Raptor codes support the system code; however, the Raptor codes need an individual pre-encoding process, i.e., a pre-encoding matrix, thus the encoding is more complex.
In order to eliminate the disadvantages of the encoding method described above, a low density generator matrix code (LDGC) is introduced. The LDGC is a linear block code and non-zero elements in its generator matrix (encoding matrix) are generally sparse. In addition, the LDGC is also a system code.
FIG. 1 illustrates a schematic diagram of a generator matrix of the LDGC. As shown in FIG. 1, a square matrix corresponding to the first L rows in the generator matrix GIgdc of the LDGC is typically an upper triangular matrix or a lower triangular matrix, and its matrix inversion may be implemented by an iterative method. x and y in FIG. 1 may be 0.
The encoding of the LDGC is to get an intermediate variable at first using a corresponding relationship between the information bits (data to be transmitted) and the intermediate variable in a system code and then to obtain an encoded code word by multiplying a generator matrix by the intermediate variable. Specifically, the encoding process is to fill d=L−K known bits in a K-bit information sequence m to generate a L-bit sequence s, then generate an L-bit intermediate variable sequence I according to an equation: I×GIdgc(0:L−1, 0:L−1)=s, and then generate a N-bit code word sequence CIdgc from the L-bit intermediate variable sequence I. After CIdgc passes through a channel, a code word sequence R is received by a receiver. For the detailed encoding process, we may refer to a patent entitled “An encoding method and apparatus and a decoding method and apparatus of low density generator matrix codes”, where I is a vector of l*L and GIdgc(0:L−1, 0:N+d−1) is a matrix with L*(N+d).
The decoding process of the LCGC is to get the intermediate variable using the generator matrix and then get the information bit based on a transformation relation between the information bits and the intermediate variable. When solving the intermediate variable, the most critical step is to carry out Gaussian elimination, and the speed of the Gaussian elimination affects directly the decoding speed of the LDGC. According to decoding requirements, GIdgct is defined as the transpose of GIdgc, It is defined as the transpose of I and the received sequence R is defined as a column vector.
In the process of acquiring the intermediate variable It based on a relation formula GIdgct×It=R in decoding, the following three elementary transformations should be performed for GIdgct:                1) row permutation: if the ith row is permuted by the jth row of GIdgct, then the ith bit is needed to be permuted by the jth bit of R;        2) row addition: if the ith row is added to the jth row of GIdgct, then the ith bit is needed to be added to the jth bit of R (modulus 2 is added); and        3) column permutation: if the ith column is permuted by the jth column of GIdgct, then the ith bit is needed to be permuted by the jth bit of R.        
The decoding of the LDGC uses a standard Gaussian elimination method in prior art such that the efficiency of the decoding is lower.